To fully understand unordered codes it is best to consider an example. For a binary vector u of length n, u=u.sub.1,u.sub.2, . . ,u.sub.n. The set of non-zero bits of vector u are hereafter referred to as the "support" of u. For instance, for n=6, if u=100101, the support of u is the set {1,4,6}. Two vectors u and v of length n are considered unordered when their supports are unordered as sets; i.e., neither of them contains the other. Thus, u=100101 and v=010101 are unordered because their corresponding supports are {1,4,6} and {2,4,6}. By contrast, the vector w=000101 which has a support of {4,6} would not be unordered relative to either u or v because its support {4,6} is a subset of the support of both u and v.
One of the early descriptions of unordered codes is by J. M. Berger, "A Note on Error Detection Codes for Asymmetric Channels", Information and Control, Vol. 4, pp. 68-73, 1961. He used the term "sum code" in which the sum of the number of 1's appearing as information (e.g., data) bits was converted to a binary representation and the complement taken for each of the resulting binary digits. Unordered codes were stated to be especially useful in error detection for asymmetric channels; i.e., those in which only one type of error occurs in which either only 1's are converted to 0's or only 0's are converted to 1's. However, Berger's code did not have error correcting capability.
More recently, unordered codes have attracted wide attention in coding theory. Among their applications are protecting write-only memories (WOM) against hostile overwrites, use in parallel asynchronous communications, and detection of asymmetric and unidirectional errors in computer memories.
Examples of optimal unordered codes from the point of view of the number of codewords they contain are the so-called "balanced" codes; i.e., the number of 1 bits (called the "weight" of a vector) is half the length of the vector. Thus, in the above example, both u and v are balanced because the number of 1 bits in each is 3 and the length is 6 bits.
Balanced codes and also balanced codes that incorporate error correction are known in the prior art. However, despite the fact that balanced codes are optimal as unordered codes, they are not easy to encode and decode except when the length n of the code is a relatively small number. Also, balanced codes are not "systematic", a term which connotes codes in which the information part of the codeword and the redundancy part of the codeword are separated. Systematic codes are convenient in most applications. Some systematic unordered codes are presented by Berger. However, the Berger codes cannot correct errors.
There is a need (1) for unordered codes which have error correcting capability and are easy to encode and decode, and (2) for a method and apparatus for encoding and decoding unordered systematic codes that provide error correction capability.